In information retrieval, users have a mental picture of content, such as images, desired to be retrieved. For example, a shopper wants to retrieve those catalog pages that match his/her envisioned style of clothing. In another example, a witness wants to help law enforcement locate a suspect in a database based on his/her memory of the face of the suspect. In a further example, a web page designer wants to find a stock photograph suitable for his/her customer's brand image. Oftentimes, such images are attempted to be retrieved based on simple keyword searching. However, such content or images (e.g., illustrations, photographs, products) are not easily identified and retrieved based on simple keyword searching In a similar manner, in other domains, such as video, document, or music retrieval, it is difficult to accurately meet a user's search needs if relying on keyword search alone.
As a result, interactive search techniques have been developed to attempt to identify and retrieve the content envisioned by the user by allowing the user to iteratively refine the results retrieved by the system. The basic idea in such techniques is to show the user candidate results, obtain feedback, and adapt the system's relevance ranking function accordingly. However, existing retrieval methods provide only a narrow channel of feedback to the system. Typically, a user refines the retrieved images (or videos, audio files, or documents) by providing binary relevance feedback (i.e., informing the system which examples are “relevant” or “irrelevant”) on exemplars provided to the user, or else attempts to tune the system parameters, such as weights on a small set of low-level features (e.g., texture, color and edges in the case of image searches). The latter is clearly a burden for a user who likely cannot understand the inner workings of the algorithm. The former feedback is more natural to supply, yet it leaves the system to infer what about those images the user found relevant or irrelevant, and therefore can be slow to converge on the user's envisioned content in practice.
A further deficiency in interactive search techniques involves the examples (images, videos, audio files, or documents) that are selected to be provided to the user for feedback. Typically, the system simply displays a screen full of top-ranked examples, leaving a user free to provide feedback on any of them. This strategy has the appeal of simultaneously showing the current results and accepting feedback. However, the examples believed to be the most relevant need not be the most informative for reducing the system's uncertainty in selecting the examples that are the closest to the user's envisioned image. As a result, the approach may fail to explore relevant portions of the feature space, and can waste interaction cycles eliciting redundant feedback. Hence, such techniques are inefficient in terms of the system's selection time as well as the user's feedback effort as a result of not providing examples to the user for which feedback would be most informative for reducing the system's uncertainty (i.e., improve the system's notion of relevance).